\section{Parser}
Con el objetivo de reconocer las expresiones regulares definidas en la gram\'atica entregada en el enunciado 
del trabajo pr\'actico, se construyo un parser LL(1) utilizando la herramienta ANTLR. Con este programa generamos un
lexer y un parser en lenguaje java que entrega como salida un \'arbol AST. Recorriendo este \'arbol podemos generar el aut\'omata 
no determin\'istico que utilizaremos para reconocer las cadenas que satisfacen la expresi\'on regular.

\subsection{Adecuación de gramáticas}
La gram\'amatica proporcionada no es la adecuada para generar un parser LL(1). Para poder generar este tipo de parsers es necesario 
eliminar la recursi\'on y factorizar a izquierda. Adem\'as, hay que forzar la precedencia de operadores para que se resuelva correctamente
al generar el \'arbol.
Luego de realizar estas transformaciones la gram\'atica resultante fue la que se detalla a continuaci\'on. Para simplificar la lectura
se muestra una gram\'atica ELL(1).\\
\\
\
$G'=<\lbrace ER,ERBIN,ERCONCAT,ERUN,ERBASE \rbrace,\lbrace caracter, |, *, +, ?, ., (, )\rbrace, P, ER >$\\
\\
\
\indent $ER 	\rightarrow	ERBIN$\\
\indent $ERBIN \rightarrow ERCONCAT\ (\ |\ ERCONCAT)^{?}$\\%tengo un error acá en \textbf{|}
\indent $ERCONCAT \rightarrow ERUN\ ERCONCAT^{?}$\\
\indent $ERUN \rightarrow ERBASE\ ($*$\ |\ $+$\ |\ $?$)^{?}$\\
\indent $ERBASE	\rightarrow \ \textbf{(}\ ER\ \textbf{)}\ $\\
\indent\indent\indent\indent\indent $|\ caracter\ $\\
\indent\indent\indent\indent\indent $|\ $.\\


\subsection{Gramática ANTLR final}
A continuaci\'on se presenta la gram\'atica final tal cual se implement\'o en ANTLR. Por convenci\'on, en ANTLR los
s\'imbolos terminales o tokens van en may\'usculas, mientras que los no terminales van en min\'usculas.\\
En primer lugar se especifican los tokens que aceptar\'a la gram\'atica y se definen los caracteres aceptados.
Luego se presentan las producciones, a las que se le agrega c\'odigo que especifica como se conformar\'a 
el \'arbol AST que se entregar\'a como salida.\\
La regla \verb+erbinary+, por ejemplo, genera un nodo \verb+OR+ del que cuelgan un nodo 
\verb+erbinary+ y un nodo \verb+erconcat+. Los signos \verb+!+ en \verb+erbase+ evitan que se generen nodos para 
los paréntesis. Por \'ultimo, los signos \verb+^+ que siguen a un terminal o no terminal indican que dicho nodo ser\'a
raiz del sub\'arbol que genera la regla.

\begin{verbatim}

OR  	: '|' ;
CL  	: '*' ;
CLP 	: '+' ;
OPC 	: '?' ;
CAR 	: ('a'..'z'|'A'..'Z'|' '|'0'..'9') ;
ANY 	: '.' ;
LPAR 	: '(';
RPAR 	: ')';

er 	:	erbinary;
erbinary:	(erca=erconcat->$erca) (OR ercb=erconcat -> ^(OR $erbinary $ercb))?;
erconcat:	erunary erconcat? -> ^(ERCONCAT erunary erconcat?);
erunary :	erbase  (CL^|CLP^|OPC^)?;
erbase	:	(LPAR! er RPAR!) | CAR | ANY;

\end{verbatim}

